package LeetCodeHot100;

/**
 * 19. 删除链表的倒数第 N 个结点
 *  给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 *  思路：1:删除链表倒数的节点，首先要遍历到倒数第n个节点，然后找到第n个节点的前后节点，然后做删除操作
 *      先确定长度，然后定位到要删除的节点，然后开删]
 *       2:
 *      或者可以使用快慢指针，快指针先到第n位，然后慢指针再跑， 这样也可以到快指针遍历到链表结尾的时候，
 *       慢指针刚好到倒数第n个节点的前一个节点上，同样利用辅助指针，跑到第n位刚好到前一个节点上
 */
public class LeetCode19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
            int listNodeLength = 0;
            ListNode temp = head;
            // 计算链表的长度
            while (temp != null){
                listNodeLength++;
                temp = temp.next;
            }
            ListNode dump = new ListNode(0,head);
            ListNode cur = dump;
            for (int i = 0; i < listNodeLength - n ; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            return dump.next;
    }


    public ListNode removeBthFormEnd1(ListNode head,int n){
        if(head == null || n == 0){
            return head;
        }
        ListNode dump = new ListNode(0,head);
        ListNode fast = dump;
        ListNode slow = dump;
        // 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 然后慢指针再走, 因为设置了辅助节点，所以判断条件是.next 不为空，即快指针到最后一个节点就结束
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        //删节点
        slow.next = slow.next.next;
        return dump.next;
    }



    /**
     * 废弃
     * @return
     */
//    public ListNode removeNthFromEnd1(ListNode head, int n) {
//
//        // 不加辅助节点的写法要判断边界条件，因为 node.next.next的情况存在, 这样写也不对，还有【1,2】这种情况，所以还是老老实实用个辅助节点
//        if(head.next == null && n==1){
//            return null;
//        }else if(head.next == null){
//            return head;
//        }
//
//        int listNodeLength = 0;
//        ListNode temp = head;
//        // 计算链表的长度
//        while (temp != null){
//            listNodeLength++;
//            temp = temp.next;
//        }
//        ListNode cur = head;
//        // 找到上一个cur的前一个节点
//        for (int i = 0; i < listNodeLength - n - 1; i++) {
//            cur = cur.next;
//        }
//        cur.next = cur.next.next;
//        return head;
//    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
